﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace neuro
{
  public class GA
  {
    public interface IValue
    {
      IParam Param { get; }
    }

    public class Value<T> : IValue
    {
      public IParam Param { get; set; }

      public T Val { get; set; }

      public override string ToString()
      {
        return Val.ToString();
      }
    }

    public interface IParam
    {
      int Length { get; }

      string Name { get; }

      IValue Decode(IList<bool> bits);
    }

    public class BoolParam : IParam
    {
      public int Length { get { return 1; } }

      public string Name { get; set; }

      public IValue Decode(IList<bool> bits)
      {
        return new Value<bool>() { Param = this, Val = bits[0] };
      }
    }

    private static int bitsForInt(int i)
    {
      return (int)Math.Ceiling(Math.Log(i, 2));
    }

    private static int decodeInt(IList<bool> bits)
    {
      int val = 0;
      for (int i = 0; i < bits.Count; ++i)
      {
        val += (int)Math.Pow(2, i) * (bits[i] ? 1 : 0);
      }
      return val;
    }

    public class IntParam : IParam
    {
      public int Min { get; set; }

      public int Max { get; set; }

      public int Length { get { return bitsForInt(Max - Min + 1); } }

      public string Name { get; set; }

      public IValue Decode(IList<bool> bits)
      {
        return new Value<int>() { Param = this, Val = Min + decodeInt(bits) % (Max - Min) };
      }
    }

    public class DoubleParam : IParam
    {
      public double Min { get; set; }

      public double Max { get; set; }

      public double Step { get; set; }

      public int Length { get { return bitsForInt((int)Math.Ceiling((Max - Min) / Step) + 1); } }

      public string Name { get; set; }

      public IValue Decode(IList<bool> bits)
      {
        return new Value<double>() { Param = this, Val = Min + (Max - Min) * decodeInt(bits) / Math.Pow(2, bits.Count) };
      }
    }

    public class ListParam : IParam
    {
      public IList<IParam> Params { get; set; }

      public int Length { get { return Params.Sum(param => param.Length); } }

      public string Name { get; set; }

      public IValue Decode(IList<bool> bits)
      {
        int pos = 0;
        IList<IValue> values = new List<IValue>();
        foreach (IParam param in Params)
        {
          values.Add(param.Decode(bits.Skip(pos).Take(param.Length).ToList()));
          pos += param.Length;
        }
        return new Value<IList<IValue>>() { Param = this, Val = values };
      }
    }

    public IList<IParam> ParamList { get; set; }

    public int GenomeLength { get { return ParamList.Sum(param => param.Length); } }

    Random random = new Random();

    private bool Flip(double prob)
    {
      return random.NextDouble() < prob;
    }

    public double MutateProb { get; set; }

    public double CrossProb { get; set; }

    public enum SelectionType
    {
      ROULETTE,
      TOURNAMENT,
    };

    public SelectionType Selection { get; set; }

    private void Mutate(Genome genome)
    {
      for (int i = 0; i < genome.Bits.Count; ++i)
      {
        if (Flip(MutateProb))
        {
          genome.Bits[i] = !genome.Bits[i];
        }
      }
    }

    private void Cross(Genome c1, Genome c2, out Genome n1, out Genome n2)
    {
      if (Flip(CrossProb))
      {
        int pos = random.Next(GenomeLength);
        n1 = new Genome(c1.Bits.Take(pos).Concat(c2.Bits.Skip(pos)).ToList());
        n2 = new Genome(c2.Bits.Take(pos).Concat(c1.Bits.Skip(pos)).ToList());
      }
      else
      {
        n1 = new Genome(c1.Bits);
        n2 = new Genome(c2.Bits);
      }
    }

    private Genome Select(IList<Genome> pop, IList<double> scores)
    {
      switch (Selection)
      {
        case GA.SelectionType.ROULETTE:
          {
            double minScore = scores.Min();
            if (minScore < 0)
            {
              scores = scores.Select(s => s - minScore).ToList();
            }
            double totalScore = scores.Sum();
            double targetScore = random.NextDouble() * totalScore;
            double score = 0;
            int i = 0;
            while (score < targetScore && i < pop.Count)
            {
              score += scores[i++];
            }
            return pop[i - 1];
          }
        case GA.SelectionType.TOURNAMENT:
          {
            int i = random.Next(pop.Count);
            int j = random.Next(pop.Count);
            return scores[i] > scores[j] ? pop[i] : pop[j];
          }
        default:
          throw new Exception();
      }
    }

    public int PopSize { get; set; }

    public int NumGens { get; set; }

    public class Genome
    {
      public Genome(Random random, int length)
      {
        Bits = new List<bool>();
        for (int i = 0; i < length; ++i)
        {
          Bits.Add(random.Next(2) == 1);
        }
      }

      public Genome(IList<bool> bits)
      {
        this.Bits = new List<bool>(bits);
      }

      public IList<bool> Bits { get; private set; }
    }

    public class Phenome
    {
      public Phenome(IList<IParam> paramList, Genome genome)
      {
        Values = new List<IValue>();
        int pos = 0;
        foreach (IParam param in paramList)
        {
          Values.Add(param.Decode(genome.Bits.Skip(pos).Take(param.Length).ToList()));
          pos += param.Length;
        }
      }

      public IList<IValue> Values { get; private set; }

      public override string ToString()
      {
        return string.Join(", ", Values);
      }
    }

    private IList<Genome> Generate()
    {
      IList<Genome> pop = new List<Genome>();
      for (int i = 0; i < PopSize; ++i)
      {
        pop.Add(new Genome(random, GenomeLength));
      }
      return pop;
    }

    public Func<Phenome, double> Eval { get; set; }

    public Phenome Run()
    {
      IList<Genome> pop = Generate();
      Phenome best = null;
      double bestScore = 0;
      for (int gen = 0; gen < NumGens; ++gen)
      {
        IList<Phenome> inds = pop.Select(genome => new Phenome(ParamList, genome)).ToList();
        IList<double> scores = inds.Select(ind => Eval(ind)).ToList();
        for (int i = 0; i < PopSize; ++i)
        {
          if (best == null || scores[i] > bestScore)
          {
            bestScore = scores[i];
            best = inds[i];
          }
        }

        Console.WriteLine(string.Format("{0} {1} {2} {3}", gen, scores.Min(), scores.Sum() / (double)scores.Count, scores.Max()));

        IList<Genome> newPop = new List<Genome>();
        for (int i = 0; i < PopSize; i += 2)
        {
          Genome i1 = Select(pop, scores);
          Genome i2 = Select(pop, scores);
          Genome c1, c2;
          Cross(i1, i2, out c1, out c2);
          Mutate(c1);
          Mutate(c2);
          newPop.Add(c1);
          newPop.Add(c2);
        }

        pop = newPop;
      }
      return best;
    }
  }
}
